package com.le.enhance.class5;

import org.junit.Test;

/**
 * 1. 判断二叉树是否是平衡二叉树
 */
public class Code_01_IsBalanceTree {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class ReturnTypeBST {
        public boolean isBST;
        public int level;

        public ReturnTypeBST(boolean isBST, int level) {
            this.isBST = isBST;
            this.level = level;
        }
    }

    public static boolean isBST(Node head) {
        return process(head).isBST;
    }

    public static boolean isBST2(Node head) {
        boolean[] res = new boolean[1];
        res[0] = true;
        getHeight(head, 1, res);
        return res[0];
    }

    // 采用递归实现
    public static ReturnTypeBST process(Node head) {
        if (head == null) {
            return new ReturnTypeBST(true, 0);
        }

        ReturnTypeBST leftInfo = process(head.left);
        if (!leftInfo.isBST) {
            return new ReturnTypeBST(false, 0);
        }
        ReturnTypeBST rightInfo = process(head.right);
        if (!rightInfo.isBST) {
            return new ReturnTypeBST(false, 0);
        }
        if (Math.abs(leftInfo.level - rightInfo.level) > 1) {
            return new ReturnTypeBST(false, 0);
        }
        return new ReturnTypeBST(true, Math.max(leftInfo.level, rightInfo.level) + 1);
    }

    // 非递归

    public static int getHeight(Node head, int level, boolean[] res) {
        if (head == null) {
            return level;
        }
        int leftInfo = getHeight(head.left, level + 1, res);
        if (!res[0]) {
            return level;
        }

        int rightInfo = getHeight(head.right, level + 1, res);
        if (!res[0]) {
            return level;
        }
        if (Math.abs(leftInfo - rightInfo) > 1) {
            res[0] = false;
        }
        return Math.max(leftInfo, rightInfo);

    }

    @Test
    public void testBST() {
        Node head = new Node(4);
        head.left = new Node(2);
        head.right = new Node(6);
        head.left.left = new Node(1);
//        head.left.left.left = new Node(1);
        head.left.right = new Node(3);
        head.right.left = new Node(7);

//        System.out.println(isBST(head));
        System.out.println(isBST2(head));
    }
}
